import java.util.Stack;

public class WiggleMaxLength {

    public int wiggleMaxLength(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        stack.push(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            int size = stack.size();
            Integer peek = stack.peek();
            if ((size % 2 == 1 && peek >= nums[i]) || (size % 2 == 0 && peek <= nums[i])) stack.pop();
            stack.push(nums[i]);
        }
        int size = stack.size();
        stack.clear();
        stack.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            int temp = stack.size();
            Integer peek = stack.peek();
            if ((temp % 2 == 1 && peek <= nums[i]) || (temp % 2 == 0 && peek >= nums[i])) stack.pop();
            stack.push(nums[i]);
        }
        return Math.max(stack.size(), size);
    }

}
